ECC technologies are commonly used in a number of applications, such as in magnetic discs, magnetic tapes, optical discs and semiconductor memories. Any ECC is aimed at detecting and possibly correcting errors in data of interest.
Considering in particular the memories, when an ECC is used, redundancy bits (also called check bits) are added to the bits of each data word, creating a code word that will be stored in the memory. For each element in the set of all possible configurations of data bits, one and only one possible configuration of redundancy bits exists. This is accomplished by means of a corresponding parity matrix that entirely defines the ECC itself. When a read operation occurs, the system recalculates the redundancy bits from the read data bits and compares the new redundancy bits with the ones read from the memory; any difference is indicative of errors in the read data bits, and can be used to correct them in some cases.
Using more or less redundancy bits makes the difference between detection and correction capability. For example, using only a single redundancy bit allows detecting a single bit error only, performing the so called “parity check”.
Another classical example is the Hamming code: given k data bits, (n−k) redundancy bits are needed to obtain a code with n-bit code words able to correct a single-bit error, under the condition that 2(n-k)≧n+1. For example, this single-bit-error capability satisfies the reliability needs of bit-oriented, bit-interleaved memories.
However, there are applications wherein tolerance for multiple errors is needed. Typical examples are multilevel flash memories that store multiple bits in the same cell; in this case, when the cell fails due to an alpha particle, it is possible that multiple bits must be corrected; other examples are bit-oriented bit-interleaved memories, wherein it would be desirable to correct “hard” multi-bit errors to increase production yield.
This higher error-correction capability of the ECC translates into an increased complexity of the parity matrix (and then of its circuital implementation). Unfortunately, no algorithm is available for designing the parity matrix automatically so as to fit specific requirements. On the contrary, the operation must be performed manually with an iterative process that attempts to optimize the parity matrix for the desired goal. However, this process is very difficult, since any update to the parity matrix (in order to approach the goal locally) can have unexpected side-effects that adversely affect the characteristics of the parity matrix on the whole. Therefore, the process of designing the parity matrix is very time consuming, and often does not allow obtaining a parity matrix that actually fits the desired requirements.
Some attempts to design parity matrixes optimized for specific applications are known in the art. For example, U.S. Pat. No. 6,219,817, which is incorporated by reference, illustrates an error-correcting and -detecting circuit applicable to solve the problem of detecting a wire fault on a bus with time-multiplexed data. Such an error-correcting and -detecting circuit makes use of a code defined by a parity matrix whose Maximum Row Weight (defined by the maximum number of “1”s on every row) is equal to 27.